|
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form: :the set of problems that can be solved by an abstract machine M using O(f(''n'')) of resource R, where ''n'' is the size of the input. Complexity classes are concerned with the rate of growth of the requirement in resources as the input ''n'' increases. It is an abstract measurement, and does not give time or space in requirements in terms of seconds or bytes, which would require knowledge of implementation specifics. The function inside the O(...) expression could be a constant, for algorithms which are unaffected by the size of ''n'',or an expression involving a logarithm, an expression involving a power of ''n'', i.e a polynomial expression, and many others. The O is read as "order of..". For the purposes of computational complexity theory, some of the details of the function can be ignored, for instance many possible polynomials can be grouped together as a class. The resource in question can either be time, essentially the number of primitve operations on an abstract machine, or (storage) space. For example, the class NP is the set of decision problems whose solutions can be determined by a non-deterministic Turing machine in polynomial time, while the class PSPACE is the set of decision problems that can be solved by a deterministic Turing machine in polynomial space. The simplest complexity classes are defined by the following factors: * The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems (an example is FP), counting problems (e.g. #P), optimization problems, promise problems, etc. * The model of computation: The most common model of computation is the deterministic Turing machine, but many complexity classes are based on nondeterministic Turing machines, boolean circuits, quantum Turing machines, monotone circuits, etc. * The resource (or resources) that are being bounded and the bounds: These two properties are usually stated together, such as "polynomial time", "logarithmic space", "constant depth", etc. Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity. Bounding the computation time above by some concrete function ''f''(''n'') often yields complexity classes that depend on the chosen machine model. For instance, the language can be solved in linear time on a multi-tape Turing machine, but necessarily requires quadratic time in the model of single-tape Turing machines. If we allow polynomial variations in running time, Cobham-Edmonds thesis states that "the time complexities in any two reasonable and general models of computation are polynomially related" . This forms the basis for the complexity class P, which is the set of decision problems solvable by a deterministic Turing machine within polynomial time. The corresponding set of function problems is FP. The Blum axioms can be used to define complexity classes without referring to a concrete computational model. ==Important complexity classes== Many important complexity classes can be defined by bounding the time or space used by the algorithm. Some important complexity classes of decision problems defined in this manner are the following: It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem. Other important complexity classes include BPP, ZPP and RP, which are defined using probabilistic Turing machines; AC and NC, which are defined using boolean circuits and BQP and QMA, which are defined using quantum Turing machines. #P is an important complexity class of counting problems (not decision problems). Classes like IP and AM are defined using Interactive proof systems. ALL is the class of all decision problems. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Complexity class」の詳細全文を読む スポンサード リンク
|